1. Field of the Invention
The present invention relates to the field circuit design and, more specifically to design of circuits for calculating cyclic redundancy check (CRC) codes.
2. Description of the Related Art
Cyclic redundancy check (CRC) codes have many uses. In computer networking, for example, a CRC code is a very powerful tool and easily implemented technique to obtain data reliability in networking. The CRC technique is used to verify the integrity of blocks of data called Frames. Using this technique, the transmitter appends an extra n bit sequence to every frame called Frame Check Sequence (FCS). FCS holds redundant information about the frame that helps the receiver detect errors in the frame. CRC is one of the most commonly used techniques for error detection in data communications.
One known hardware implementation of a bit-wide CRC generator is a simple linear feedback shift register (see FIG. 1.). For example, FIG. 1 illustrates a bit wide CRC generator for the polynominal G(x)=1+X+X.sup.3 +X.sup.5. While such a circuit is simple and can run at very high clock speeds, it suffers from the limitation that the stream must be bit-serial. This means that n clock cycles will be required to calculate the CRC values for an n-bit data stream. In many high speed data networking applications where data frames need to be processed at high speeds this latency is intolerable and hence, implementation of CRC generation and checking on a parallel stream of data becomes desirable.
A byte-wide CRC generator can be implemented to generate CRC for an 8-bit wide data stream in one clock cycle as opposed to 8 clock cycles with a conventional CRC generator (and, other width CRC generators can be implemented for other width data streams). In addition, several software implementations have been proposed to compute the CRC for a multi-bit data stream. See, e.g., Perez et al., Byte wise CRC calculations, IEEE Micro. 3(3):40-50 June, 1983 and Pandeya et al., Parallel CRC lets many lines use one circuit, Computer Design, 14(9):87-91, September, 1975.